package com.fw.structure.josephu;

import lombok.*;

/**
 * @Author:yanwei
 * @Date: 2021/1/16 - 17:41
 * <p>
 * 约瑟夫 小孩出圈问题，单向环形链表的实现方式
 */
public class JosePhuLinkList {

    public static void main(String[] args) {

        SingRingLinkList singRingLinkList = new SingRingLinkList();
        singRingLinkList.addBoys(10);
        singRingLinkList.showLinkList();
        singRingLinkList.jumpLinkList(5,5);
        singRingLinkList.showLinkList();

    }


}


/**
 * 单向链表类
 */
class SingRingLinkList {

    // 添加一个头节点 自身链接自身
    private Boy first = new Boy(-1, null);

    // 添加圈
    public void addBoys(int boys) {
        // 参数验证
        if (boys <= 0 || first.getNext() != null) return;
        Boy boyTemp = null;
        for (int i = 0; i < boys; i++) {
            // 环形列表准备
            Boy boy = new Boy();
            boy.setNo(i);
            if (i == 0) {
                // 第一个元素
                first = boy;
                // 做成环形结构
                first.setNext(first);
                boyTemp = first;
            } else {
                // 其它元素
                boyTemp.setNext(boy);
                boyTemp = boyTemp.getNext();
                boyTemp.setNext(first);
            }

        }

    }


    // 遍历小孩
    public int showLinkList() {
        if (first.getNo() == -1) return - 1;

        int index = 0;
        Boy boyTemp = first;
        while (true) {
            System.out.printf("当前编号 %d \n", boyTemp.getNo());
            boyTemp = boyTemp.getNext();
            if (boyTemp.getNo() == first.getNo()) break;

            index ++;
        }
        return index;
    }


    // 小孩出圈

    /**
     *
     * @param startNo 第几个开始
     * @param countNum 那个出圈
     */
    public void jumpLinkList(int startNo , int countNum){
        int size = this.showLinkList();
        if ( startNo == 1 || first.getNo() == -1 || startNo > size || countNum  > (size - startNo +1) ) return;


        // 先算出从几个开始的 no值
        Boy temBoy = first;
        Boy crryBoy = null;
        while (true){
            if (temBoy.getNo() == startNo) {
               // 开始了，数小孩 数出队列。
                for (int i = 0; i < countNum; i++) {
                    System.out.printf("数出的小孩编号为:%d \n",temBoy.getNo());
                    // 将当前小孩 变成废子。

                    temBoy = temBoy.getNext();
                    crryBoy.setNext(temBoy);
                 if (temBoy.getNo() == first.getNo())
                     // 截至
                     return;
                }
            }

            crryBoy = temBoy;
            temBoy = temBoy.getNext();
            if (temBoy.getNo() == first.getNo())
                // 找不到对应的startNo 编号
                return;

        }


    }


    // 清除链表
    public void clearLinkList() {
        first = new Boy(-1, null);
        // gc
    }


}


/**
 * 小孩类
 */
@Getter
@Setter
@AllArgsConstructor
@NoArgsConstructor
class Boy {
    private int no;
    private Boy next;

}
